class Solution03 {
    // 全局变量
    int ret;
    // 路径结果
    int path;
    int target;

    public int findTargetSumWays(int[] nums, int _target) {
        target = _target;
        dfs(nums, 0);
        return ret;
    }

    public void dfs(int[] nums, int pos) {
        if (pos == nums.length) {
            if (path == target) {
                ret++;
            }
            return;
        }
        // 两种选择
        // 加法
        path += nums[pos];
        dfs(nums, pos + 1);
        // 回溯 ---> 恢复现场
        path -= nums[pos];

        // 减法
        path -= nums[pos];
        dfs(nums, pos + 1);
        // 回溯 ---> 恢复现场
        path += nums[pos];
    }
}